package com.动态规划.基础;

public class 使用最小花费爬楼梯 {

    public static int minCostClimbingStairs(int[] cost) {
        //确定dp[i]数组的含义：dp[i]表示到达第i台阶的最低花费,默认第一步都不需要支付费用。
        int[] dp=new int[cost.length+1];
        //初始化dp
        dp[0]=0;
        dp[1]=0;
        //遍历
        for(int i=2;i<=cost.length;i++){
            dp[i]=Math.min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        for(int i=0;i<=cost.length;i++){
            System.out.print(dp[i]+",");
        }
        System.out.println();
        return dp[cost.length];
    }
    //优化
    public static int minCostClimbingStairs2(int[] cost) {
        //确定dp[i]数组的含义：dp[i]表示到达第i台阶的最低花费,默认第一步都不需要支付费用。
        int[] dp=new int[2];
        //初始化dp
        dp[0]=0;
        dp[1]=0;
        int minCost=0;
        //遍历
        for(int i=2;i<=cost.length;i++){
            minCost=Math.min(dp[0]+cost[i-2],dp[1]+cost[i-1]);
            dp[0]=dp[1];
            dp[1]=minCost;
        }
        return minCost;
    }
    public static void main(String[] args) {
        int[] cost={1,100,1,1,1,100,1,1,100,1};
        System.out.println(minCostClimbingStairs2(cost));
    }
}
